# 

class Solution:     
    def solveNQueens(self, n: int):
        matrix=[[0 for _ in range(n)] for _ in range(n)]
        result=[]
        # self.updateQueen(matrix,3,1,n,1)
        # for j in matrix:
        #     print(j)
        def updateQueen(x,y,n,value):
        # print(x,y)
            for i in range(n):
                matrix[x][i]+=value
                matrix[i][y]+=value
            for j in range(1,min([x+1,y+1])):
                matrix[x-j][y-j]+=value
            for j in range(1,min([y+1,n-x])):
                matrix[x+j][y-j]+=value
            for j in range(1,min([n-y,x+1])):
                matrix[x-j][y+j]+=value
            for k in range(1,min([n-y,n-x])):
                matrix[x+k][y+k]+=value     
        def insertQueen(n,sets,x,y):
            if len(sets)==n:
                result.append(sets[:])
                return 
            newsets=sets[:]
            for j in range(n):
                if matrix[x+1][j]==0:
                    newsets.append([x+1,j])
                    updateQueen(x+1,j,n,1)
                    insertQueen(n,newsets,x+1,j)
                    updateQueen(x+1,j,n,-1)
                    newsets.pop()
        insertQueen(n,[],-1,0)
        resultmap=[]
        for re in result:
            board=[["." for _ in range(n)] for _ in range(n)]
            for index in re:
                board[index[0]][index[1]]="Q"
            resultmap.append(["".join(row) for row in board])     
        return resultmap


